package com.bjpowernode.linkedlist;

import com.sun.corba.se.impl.orbutil.HexOutputStream;

import java.util.Stack;

/**
 * @author wuyuecai
 * @create 2021-06-02 19:57
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试一把
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(5, "入云龙", "公孙胜");
        HeroNode hero6 = new HeroNode(8, "关胜", "大刀");
        HeroNode hero7 = new HeroNode(7, "秦明", "霹雳火");
        HeroNode hero8 = new HeroNode(8, "呼延灼", "双鞭");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //每次添加都把节点添加到链表的末尾
        singleLinkedList.addNode(hero1);
        singleLinkedList.addNode(hero3);
        singleLinkedList.addNode(hero2);
        singleLinkedList.addNode(hero4);
        //按照节点编号的顺序添加,生成两个单链表
//        singleLinkedList.addOrderNode(hero1,singleLinkedList.getHead());
//        singleLinkedList.addOrderNode(hero3,singleLinkedList.getHead());
//        singleLinkedList.addOrderNode(hero2,singleLinkedList.getHead());
//        singleLinkedList.addOrderNode(hero4,singleLinkedList.getHead());

//        singleLinkedList.addOrderNode(hero5,singleLinkedList.getHead2());
//        singleLinkedList.addOrderNode(hero6,singleLinkedList.getHead2());
//        singleLinkedList.addOrderNode(hero7,singleLinkedList.getHead2());
//        singleLinkedList.addOrderNode(hero8,singleLinkedList.getHead2());

        System.out.println("第一个单链表");
        singleLinkedList.showLinkedList(singleLinkedList.getHead());
        singleLinkedList.delNode(4);
        System.out.println("删除之后链表");
        singleLinkedList.showLinkedList(singleLinkedList.getHead());

        System.out.println();
//        System.out.println("第二个单链表");
//        singleLinkedList.showLinkedList(singleLinkedList.getHead2());
//
//        System.out.println("合并之后的单链表");
//        singleLinkedList.showLinkedList(mergeLinkedList(singleLinkedList.getHead(),singleLinkedList.getHead2()));

        //修改之前的链表
//        System.out.println("修改之前的链表");

//        System.out.println("反转之前的链表");
//        singleLinkedList.showLinkedList(singleLinkedList.getHead());
        //查找倒数第k个节点
//        HeroNode node = searchNode(singleLinkedList.getHead(), 0);
//        System.out.println("倒数第k个节点为："+node);

        //反转之后的链表
//        System.out.println("反转之后的链表");
//        reverse(singleLinkedList.getHead());
//        singleLinkedList.showLinkedList(singleLinkedList.getHead());

        //逆序输出单链表
//        System.out.println("逆序输出单链表");
//        reversedPrint(singleLinkedList.getHead());


        //单链表中有效节点的个数
//        System.out.println(numNode(singleLinkedList.getHead()));
//
//        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟卢俊义");
//        singleLinkedList.update(newHeroNode);
//
//        //修改之后的链表
//        System.out.println("修改之后的链表");
//        singleLinkedList.showLinkedList();

        //删除之后的链表
//        singleLinkedList.delNode(2);

//        System.out.println(numNode(singleLinkedList.getHead()));
//        System.out.println("删除之后的链表");
//        singleLinkedList.showLinkedList();
    }

    //将两个有序单链表合并，合并之后的单链表依然有序
    //思路：1.创建一个单链表用于存储合并之后的节点 2.创建两个有序单链表，分别遍历每次取出节点存入新的单链表中
//    public static HeroNode mergeLinkedList(HeroNode head1,HeroNode head2){
//        HeroNode mergeNode = new HeroNode(0, "", "");//创建合并链表
//        if(head1.next != null && head2 != null){
//            HeroNode temp = head2.next;//辅助节点，用于遍历单链表
//            HeroNode next = null;//用于记录有序链表中要合并节点的下一个节点
//            boolean flag = false;
//            HeroNode temp2 = mergeNode;//辅助节点，用于遍历合并链表
//            if(temp2.next == null){//如果合并链表为空直接让他指向第一个有序链表
//              temp2.next = head1.next;
//            }
//            while (temp != null){
//                if(temp2.next.no > temp.no ){//这时找到的是要插入位置的上一个节点,所以只能用temp2 = mergeNode，而不能用temp2 = mergeNode。另外temp = head2.next,只能这样写，因为里面要有next属性指向要取走元素的下一个节点
//                    next = temp.next;//记录要插入节点的下一个节点
//                    temp.next = temp2.next;//先将要插入的节点指向合并链表中的要插入位置节点之后的节点
//                    temp2.next = temp;//将在合并链表要插入位置的节点指向要插入的节点
//                    temp = next;//将有序链表中temp指向下一个节点
//                }else if(temp.no == temp2.next.no){
//                    flag = true;
//                }
//                //将合并链表的指针后移
//                if(temp2.next == null){
//                    temp2.next = temp;
//                    temp = temp.next;
//                    break;
//                }else {
//                    temp2 = temp2.next;
//                }
//            }
//            if(flag){
//                System.out.println("编号已存在，插入不成功");
//            }else {
//                return mergeNode;
//            }
//
//        }else if(head1.next == null && head2.next != null){
//            mergeNode.next = head2.next;
//            return mergeNode;
//        }else if(head1.next != null && head2.next == null){
//            mergeNode.next = head1.next;
//            return mergeNode;
//        }
//
//        return null;
//    }

    //将单链表反转。思路：1.创建一个反转链表，然后从原来的单链表依次取出节点使用头插法放入新的反转链表中
    // 2.头插法意思是每次从原来的链表取出节点后将节点的next域执行反转链表的最后一个节点，将反转链表的头节点指向该节点
    public static void reverse(HeroNode head){
        if(head.next == null ||head.next.next == null){
            return;//如果没有节点或者只有一个节点则不需要反转
        }
        HeroNode temp = head.next;
        HeroNode next = null;//用来标记要取出节点的下一个节点
        HeroNode reverseNode = new HeroNode(0,"","");//新建一个反转链表
        while (temp != null){
            next = temp.next;//先让要取出节点的下一个节点存到next变量中
            temp.next = reverseNode.next;//将新节点的next属性指向反转链表的最后一个节点
            reverseNode.next = temp;//将反转链表头节点指向新节点
            temp = next;//将temp指向原来链表的下一个节点
        }
        head.next = reverseNode.next;//将原来链表的头节点指向反转链表

    }

    //将单链表逆序输出。思路：1.先将单链表遍历取出，并将节点放入栈中2.从栈中取出数据就实现了单链表的逆序输出
    public static void reversedPrint(HeroNode head){
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        //创建一个栈用于存放取出的节点数据
        Stack<HeroNode> sta = new Stack<>();
        while (temp.next != null){
            sta.push(temp.next);
            temp = temp.next;
        }
        //从栈中取出数据，即是单链表的逆序输出,栈的特点是先进后出
        while (sta.size() > 0){
            System.out.println(sta.pop());
        }

    }

    //查找单链表中倒数第k个节点.思路：
    // 1.遍历链表查找到链表有效节点个数num
    // 2.num-k = size表示k前面有size个节点，从头开始遍历size个节点，第size+1个节点就是要找的节点
    public static HeroNode searchNode(HeroNode head,int k){
       //第一种方法
//        if(head.next == null){
//            return null;//链表为空
//        }
//        HeroNode temp = head;
//        int size = numNode(head) -k;//表示要查找节点的前面有size个节点
////        int counter = 0;//用counter == size,判断什么时候遍历完size个点
//        if(k <= 0 || k > numNode(head)){
//            return null;//对k做有效校验
//        }
//        for (int i = 0; i < size; i++) {
//            //指针后移
//            temp = temp.next;
//        }
//        return temp.next;


//        第二种方法
//        if(head.next == null){
//            return null;//链表为空
//        }
//        if(k <= 0 || k > numNode(head)){
//            return null;//对k做有效校验
//        }
        HeroNode temp = head.next;
        int size = numNode(head) -k;//表示要查找节点的前面有size个节点
        int counter = 0;//用counter == size,判断什么时候遍历完size个点
        while (temp != null) {
            if (counter == size) {
                return temp;
            }
            counter++;
            //指针后移
            temp = temp.next;
        }
        return null;
    }


    //查找单链表中有效节点的个数,不包括头节点
    public static int numNode(HeroNode head){
        HeroNode temp = head;
        int counter = 0;//计数器，记录有效节点的个数
        while (true){
            if(temp.next == null){
                break;
            }
            counter++;
            //后移指针直到最后一个节点
            temp = temp.next;
        }
        return counter;
    }
}
//用于编写链表中的操作，比如添加节点，显示链表节点信息，增删改查的方法封装
class SingleLinkedList{
    //先初始化一个头节点，头节点不能动，不然会找不到整个链表信息
    private HeroNode head = new HeroNode(0,"","");
    private HeroNode head2 = new HeroNode(0,"","");

    public HeroNode getHead(){
        return head;
    }
    public HeroNode getHead2(){
        return head2;
    }

    //按照节点编号进行查找，然后删除该节点。注意这个方法只删除第一个找到的节点
    public void delNode(int no){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if(temp.next == null){
                break;
            }
            if(temp.next.no == no){
                flag = true;
                break;
            }
            //后移节点，才能遍历整个链表
            temp = temp.next;
        }
        if(flag){
            //删除的关键是找到要删除节点的前一个节点，使用temp = head.next的辅助节点则找不到删除节点的前一个节点
            temp.next = temp.next.next;

        }else {
            System.out.println("编号不存在，删除失败");
        }

    }


    //按照节点的编号进行查找，然后修改信息
    public void update(HeroNode newHeroNode){
        HeroNode temp = head.next;
        boolean flag = false;//如果找到了则进行修改，没有找到，则不进行修改并给出提示信息
        while (true){
            if(temp == null){//刚开始temp指头节点的下一个节点，每次temp后移之后指下一个节点。也就是永远指下一个节点
                break;//代表链表已经遍历完
            }
            if(temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            //temp后移才能遍历整个链表
            temp = temp.next;
        }
        if(flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else {
            System.out.println("需要修改信息的节点编号不存在，请检查节点编号是否存在");
        }

    }
    //添加节点时，按照节点的no进行有序添加
    public void addOrderNode(HeroNode heroNode,HeroNode head){
        //思路：1.使用辅助节点遍历链表，查找要添加的节点位置，如果要添加的节点编号在temp.next.no和temp.no之间则新的节点位置就在他们之间
        //2.然后进行新节点.next = temp.next,和temp = 新节点操作进行添加
        HeroNode temp = head;
        boolean flag = false;//如果添加节点的编号已经存在则输出提示信息，flag用于标识节点标号是否存在
        while (true){
            if(temp.next == null){//temp.next == null意味着链表为空或者前面的节点编号没有比新节点编号大的，那么就可以直接在temp节点之后进行添加了，且新节点是最后一个节点
                break;
            }
            if(temp.next.no > heroNode.no){//这个条件代表着temp后面的那个节点编号大于新节点编号，那么temp节点编号则小于新节点编号，因为temp是从头开始遍历的
                break;
            }else if(temp.next.no == heroNode.no){//这个条件是如果temp后面的节点编号和新节点编号相同那么要有提示信息，并且添加不成功
                flag = true;
                break;
            }
            //后移temp，要遍历整个链表
            temp = temp.next;
        }
        if(flag){
            System.out.println("节点编号已经存在，添加不成功");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }


    }



    //添加节点到单项链表中，不考虑编号顺序的情况
    //思路：1.每次添加节点到链表的最后位置2.先查找链表的最后位置3.然后让最后位置的next域指向当前节点的地址
    public void addNode(HeroNode heroNode){
        //因为头节点不能动，所以创建一个辅助节点，用于添加节点
        HeroNode temp = head;
        //遍历链表找到最后一个位置
        while (true){
            if(temp.next == null){
                break;
            }
            //如果temp.next不为空,那么把temp.next赋值给辅助节点temp(temp本身就是一个对象，这个对象有next属性，并且next变量还是HeroNode的类型，意味着，next也是一个地址)
            //让它继续向后寻找知道temp.next为空为止
            temp = temp.next;
        }
        //当退出循环时，意味着temp.next为空了,将新节点的地址赋给temp.next
        temp.next = heroNode;
    }

    //显示链表中的节点信息
    //思路：1.先判断链表是否为空2.使用辅助节点从头节点的下一个节点开始遍历3.当辅助节点为空时链表遍历结束
    public void showLinkedList(HeroNode head){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (true){
            if(temp == null){
                break;
            }
            //当temp不为空时，输出当前节点信息
            System.out.println(temp);
            //当temp不为空时，将temp.next即当前节点下一个节点地址赋给temp，如果temp.next为空即temp为空，则结束循环
            temp = temp.next;
        }
    }

}

//用于存储链表中的节点：包含数据域和next域。每一个HeroNode对象就是一个节点信息
class HeroNode{
    public int no ;//英雄编号
    public String name;//英雄姓名
    public String nickName;//英雄昵称
    HeroNode next;//存储链表的下一个元素的地址的HeroNode变量

    public HeroNode() {
    }

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }
    //重写tostring方法用于显示节点的信息，注意把next变量给去掉，不然前面的节点显示时会把后面的节点信息也一块显示了，
    // 因为，next就表示下一个节点的地址值
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\''+
                '}';
    }
}